package 面向对象;
/**
 前提基础:内部类和递归
 数据结构之链表: 根节点root<实例对象>包括(节点数据<data>,下一个节点指向<next对象>)
             下一节点next<实例对象>同样包括(节点数据<data>，下一个节点指向<next对象>)
 链表是一种线性表，但不会按照线性的顺序存储数据，而是在没个节点存放下一个节点的指针。
 链表与数组:
 链表适合插入，删除  不宜过长，否则性能下降
 数组适合查找，遍历  长度固定
 */

public class 数据结构之链表
{
	public static void main(String[] args)
	{
		NodeManager nm=new NodeManager();
		System.out.println("========add========");
		nm.add(9);
		nm.add(15);
		nm.add(4);
		nm.add(8);
        nm.add(16);
		nm.add(3);		
		nm.print();
		System.out.println("=========del========");
		nm.del(4);
		nm.print();
		System.out.println("========find========");
		System.out.println(nm.find(4));
		System.out.println("========updata======");
		nm.updata(8,5);
		System.out.println("======insert=======");
		nm.insert(2,4);
		nm.print();
	}
}

class NodeManager
{
	private Node root;//根节点
	private int current;//节点当前位置  0  1  2  3

	//增加节点
	public void add(int data)
	{
		if (root == null)
		{
			root = new Node(data);
		}
		else
		{
			root.addNode(data);
		}
	}
	//删除指定节点
	public void del(int data)
	{
		//如果删除的数据是根节点，只需后面的往前挪就行
		if (root.getData() == data)
		{
		    root = root.next;//链表，next挪到root，相当于后面一串都挪动了
		}
		else
		{
			root.delNode(data);//如果删除的不在根节点，调用内部类delNode方法递归
		}
	}
	//打印所有节点
	public void print()
	{
		if (root != null)
		{
			System.out.print(root.getData() + "->");
			root.printNode();
			System.out.println();
		}
	}
	//查找节点是否存在
	public boolean find(int data)
	{
		if (root == null)return false;
		if (root.getData() == data)
		{
			return true;
		}
		else
		{
			return root.findNode(data);// 不要忘记return
		}

	}//修改节点
	public void updata(int olddata,int newdata)
	{
		if(this.find(olddata)){
			if(root.getData()==olddata){
				root.setData(newdata);
				System.out.println("修改成功.即将打印全部");
				this.print();
			}else{
				root.updataNode(olddata,newdata);
				System.out.println("修改成功.即将打印全部");
				this.print();
			}
		}else{
			System.out.println("找不到old数据 "+olddata+" 修改失败");
		}
		
		
	}
	//序号前面插入
	public void insert(int index, int data)
	{
		current=0;
		Node newnode=new Node(data);
		if(index<0)return;
		if(index==current){
			newnode.next=root;
			root=newnode;
		}else{
			root.insertNode(index,data);
		}
	}

	private class Node
	{
		private int data;//节点数据
		private Node next;//自身作为属性，节点的下一个引用

		public Node(int data)
		{
			this.data = data;
		}
		public void setData(int data)
		{
			this.data = data;
		}
		public int getData()
		{
			return data;
		}
		//增加节点
		public void addNode(int data)
		{
			if (this.next == null)//第一层this为root，如果root.next为空，添加到root.next
			{
				this.next = new Node(data);
			}
			else//否则，递归，下一层的this变为root.next
			{
				this.next.addNode(data);
			}
		}
		//删除节点
		public void delNode(int data)
		{
			if (this.next != null)
			{//这里的this是root，需要next非空才能进行下面判断
				if (this.next.data == data)
				{//同理向前挪动
					this.next = this.next.next;
				}
				else
				{//root.next还不是，递归到下一层，下一层的this变为root.next
					this.next.delNode(data);
				}
			}
		}
		//打印所有节点
		public void printNode()
		{
			if (this.next != null)
			{
				System.out.print(this.next.data + "->");
				this.next.printNode();
			}
		}
		//查询节点是否存在
		public boolean findNode(int data)
		{
			if (this.next != null)
			{
				if (this.next.data == data)
				{
					return true;
				}
				else
				{
					return this.next.findNode(data);//不要忘记return
				}
			}
			return false;
		}
		//修改节点
		public void updataNode(int olddata,int newdata)
		{
			if(this.next.data==olddata){
				this.next.data=newdata;
			}else{
				this.next.updataNode(olddata,newdata);
			}
		}
		//插入节点
		public void insertNode(int index, int data)
		{
			current++;
			if(this.next==null)return;
			if(index==current){
				Node newnode=new Node(data);
				newnode.next=this.next;
				this.next=newnode;
			}else{
				this.next.insertNode(index,data);
			}
		}
	}
}
